#include "disjoint_set.h"
#include "debug_func.h"
#include "stlhelper.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using std::list;
using std::vector;
using std::deque;
using std::pair;
using std::cerr;


namespace disjoint_set_private
{


const unsigned LIMIT = 500;

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
//
//	t_super_cluster
//
//
// 			when merging large (> LIMIT) clusters, just put them in a
//			super_cluster instead of
//			going through each cluster and repointing members
//
struct op_large_cluster
{	bool operator() (p_cluster_id a) const	{	return a->ids.size() > LIMIT;	} };

//
//	destructor frees member clusters
//
t_super_cluster::~t_super_cluster()
{
	// free member clusters
	iter ii =  clusters.begin();
	iter end = clusters.end();
	while (ii != end)
	{
		delete *ii;
		++ii;
	}
}


//
//	add new child cluster
//
p_cluster_id		t_super_cluster::add_new_cluster(unsigned id1, unsigned id2)
{
	p_cluster_id new_cluster = new t_cluster_id(this);
	new_cluster->ids.push_back(id1);
	new_cluster->ids.push_back(id2);
	// add to both clusters and small_clusters
	clusters.push_back(new_cluster);
	small_clusters.push_back(new_cluster);
	total_size += 2;
	return new_cluster;
}



//
//	swallow other's clusters
//
t_super_cluster& t_super_cluster::engulf(t_super_cluster& other)
{
	assert (&other != this);

	// other's clusters now part of this supercluster
	iter ii = other.clusters.begin();
	iter end = other.clusters.end();
	while (ii != end)
		(*ii++)->supercluster = this;

	// take over the small_clusters of other
	small_clusters.splice(small_clusters.end(), other.small_clusters,
							other.small_clusters.begin(),  other.small_clusters.end());

	// splice the clusters of other (these are hence owned by me)
	clusters.splice(clusters.end(), other.clusters,
								other.clusters.begin(),  other.clusters.end());

	// total size is the sum of both of us
	total_size += other.total_size;


	// merge clusters if small
	compress();

	assert(other.clusters.empty());
	other.total_size = 0;

	return other;
}

//
//	merge constituent clusters if small
//
void t_super_cluster::compress()
{

	// remove all big clusters
	small_clusters.remove_if(op_large_cluster());


	//
	// ii points to one past the beginning
	//
	iter ii = ++small_clusters.begin();
	iter end = small_clusters.end();

	while (ii != end)
	{
		//
		// put the contents of every cluster into first cluster ...
		//
		p_cluster_id first_cluster = small_clusters.front();
		list<unsigned>* ids = &small_clusters.front()->ids;

		//
		// ... until it is full
		//
		while (ii != end)
		{
			//
			// All IDs in cluster to be merged point to first cluster
			//
			list<unsigned>::iterator jj		= (*ii)->ids.begin();
			list<unsigned>::iterator jj_end	= (*ii)->ids.end();
			for (;jj != jj_end; ++jj)
				(*id_to_p_cluster)[*jj] = first_cluster;

			//
			// Splice all IDs in cluster to be merged into first and delete
			//
			ids->splice(ids->end(),  (**ii).ids);
			delete *ii;

			//
			// delete iterator after incrementing past it
			//		Do not increment ghosts!
			//
			clusters.remove(*ii);
			iter erase_cluster = ii++;
			small_clusters.erase(erase_cluster);

			//
			// if reached limit, do not merge with that cluster ever again
			//
			if (ids->size() >= LIMIT)
			{
				small_clusters.erase(small_clusters.begin());
				break;
			}
		}


		//
		// any more clusters to merge?
		//
		if (small_clusters.size() <= 1)
			break;

		//
		// ii points to one past the beginning again (see begin of this func)
		//
		ii = ++small_clusters.begin();
	}
}


//________________________________________________________________________________________

//	swap

//________________________________________________________________________________________
void swap(t_super_cluster& a, t_super_cluster& b)
{
	a.clusters.swap(b.clusters);
	a.small_clusters.swap(b.small_clusters);
	std::swap(a.index,  b.index);
	std::swap(a.total_size,  b.total_size);
	std::swap(a.id_to_p_cluster,  b.id_to_p_cluster);
}
bool operator < (const t_super_cluster& a, const t_super_cluster& b)
{	return a.total_size < b.total_size;	}



//________________________________________________________________________________________

//	get_new_supercluster

//			allocate new supercluster

//________________________________________________________________________________________
t_super_cluster& get_new_supercluster(	deque<t_super_cluster>&	super_clusters,
										deque<unsigned>&		free_super_clusters,
										deque<p_cluster_id>&	id_to_p_cluster)
{
	//
	//	if no free ones available to be reused, allocate from memory
	//
	if (free_super_clusters.empty())
	{
		unsigned index = super_clusters.size();
		super_clusters.insert(super_clusters.end(),  t_super_cluster(index, id_to_p_cluster));
		free_super_clusters.push_back(index);
	}

	// get index of next free super_cluster
	unsigned next = free_super_clusters.back();
	free_super_clusters.pop_back();

	return super_clusters[next];
}

//________________________________________________________________________________________

//	free_supercluster

//________________________________________________________________________________________
void free_supercluster(     t_super_cluster& cluster,
							deque<unsigned>& free_super_clusters)
{
	assert(cluster.clusters.empty());
	free_super_clusters.push_back(cluster.index);
}



//________________________________________________________________________________________

//	sort deque of unsigned by size then by index of first element

//________________________________________________________________________________________
struct op_sort_deque_u_by_size
{
	bool operator ()( vector<unsigned>& a, vector<unsigned>& b) const
	{
		if (a.size() != b.size())
			return a.size() < b.size();
		if (a.size() == 0)
			return false;
		return a[0] < b[0];
	}
};

void output_sorted_clusters(deque<t_super_cluster>&				super_clusters,
							std::deque<std::vector<unsigned> >&	output_clusters)
{
	//
	// Finish: copy to output
	//
	//
	for (unsigned i = 0; i < super_clusters.size(); ++i)
	{
		// ignore empty super_clusters
		if (super_clusters[i].clusters.empty())
			continue;


		// add empty vector to output cluster
		output_clusters.push_back(std::vector<unsigned>());
		output_clusters.back().reserve(super_clusters[i].total_size);

		// add each sub-cluster to output cluster
		t_super_cluster::iter ii = super_clusters[i].clusters.begin();
		t_super_cluster::iter end = super_clusters[i].clusters.end();
		for (; ii != end; ++ii)
			// *ii is p_cluster_id
			output_clusters.back().insert(	output_clusters.back().end(),
											(*ii)->ids.begin(),
											(*ii)->ids.end());

		// sort each cluster of ids
		sort(output_clusters.back().begin(), output_clusters.back().end());
	}

	// sort output clusters by size and then index of first id
	sort_with_swaps(output_clusters, op_sort_deque_u_by_size());

}

}












